/**
 * 406. 根据身高重建队列
 * https://leetcode-cn.com/problems/queue-reconstruction-by-height/
 */
const { displayNestedArray } = require('../../libs/public');

const invalid = [Infinity, -Infinity];

/**
 * @param {any[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {([number, number])[]} heap
 * @param {number} length
 */
function resolveHeap(heap, length) {
  let i = Math.floor(length / 2) - 1;
  let left = 0;
  let right = 0;
  for (; i >= 0; i -= 1) {
    left = i * 2 + 1;
    right = left + 1;
    const leftVal = heap[left];
    const rightVal = right >= length ? invalid : heap[right];
    const value = heap[i];
    if (value[0] < leftVal[0] && value[0] < rightVal[0]) {
      continue;
    }
    if (value[0] === leftVal[0] && value[0] === rightVal[0]) {
      if (value[1] >= leftVal[1] && value[1] >= rightVal[1]) {
        continue;
      }
      if (leftVal[1] > rightVal[1]) {
        swap(heap, i, left);
      } else {
        swap(heap, i, right);
      }
      continue;
    }
    if (leftVal[0] < rightVal[0]) {
      if (
        leftVal[0] < value[0]
        || (leftVal[0] === value[0] && leftVal[1] > value[1])
      ) {
        swap(heap, i, left);
      }
      continue;
    }
    if (rightVal[0] < leftVal[0]) {
      if (
        rightVal[0] < value[0]
        || (rightVal[0] === value[0] && rightVal[1] > value[1])
      ) {
        swap(heap, i, right);
      }
      continue;
    }
    if (leftVal[1] > rightVal[1]) {
      swap(heap, i, left);
    } else {
      swap(heap, i, right);
    }
  }
}

/**
 * @param {number[][]} people
 * @return {number[][]}
 */
function reconstructQueue(people) {
  let { length } = people;
  const indexes = new Array(length).fill(0);
  for (let i = 1; i < length; i += 1) {
    indexes[i] = i;
  }
  const result = new Array(length);
  while (length > 0) {
    resolveHeap(people, length);
    const [p] = people;
    result[indexes[p[1]]] = p;
    indexes.splice(p[1], 1);
    length -= 1;
    swap(people, 0, length);
  }
  return result;
}

console.log(displayNestedArray(reconstructQueue([[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]])) === '[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]');
console.log(displayNestedArray(reconstructQueue([[6, 0], [5, 0], [4, 0], [3, 2], [2, 2], [1, 4]])) === '[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]');
